#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define y1 y_alpha_1

using namespace std;

using ll = long long;
using db = double;
using vec = vector<int>;
using pii = pair<int,int>;

int read() {
	int x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-',ch = getchar();
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
	return f ? -x : x;
}

const int N = 1e6 + 10;
const int B = 5e5 + 5;

int c[N][2],n;
char s[B];

void solve() {
	scanf("%s",s + 1); n = strlen(s + 1); for(int i = -n;i <= n;i++) c[i + B][0] = c[i + B][1] = 0; int now = 0;
	for(int i = 1;i <= n;i++) c[now + B][s[i] - '0']++,now += s[i] == '0' ? - 1 : 1;
	now = 0;
	for(int i = 1;i <= n;i++) {
		if(c[now + B][0] && c[now + B - 1][1]) c[now + B][0]--,now--,putchar('0');
		else if(c[now + B][1]) c[now + B][1]--,now++,putchar('1');
		else c[now + B][0]--,now--,putchar('0');
	}
	puts("");
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	for(int T = in;T;T--) solve();
	return 0;
}
